package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1081 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        public String smallestSubsequence(String s) {
            boolean[] visited = new boolean[26];
            int[] remainCnt = new int[26];
            for (int i = 0; i < s.length(); i++) {
                remainCnt[s.charAt(i) - 'a']++;
            }

            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (!visited[ch - 'a']) {
                    while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
                        if (remainCnt[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                            visited[sb.charAt(sb.length() - 1) - 'a'] = false;
                            sb.deleteCharAt(sb.length() - 1);
                        } else {
                            break;
                        }
                    }
                    visited[ch - 'a'] = true;
                    sb.append(ch);
                }
                remainCnt[ch - 'a'] -= 1;
            }
            return sb.toString();
        }
    }


    class Solution_Wrong_thought {
        public String smallestSubsequence(String s) {
            LinkedHashMap<Character, Character> orderedMap = new LinkedHashMap<>();

            for (char ch : s.toCharArray()) {
                if (!orderedMap.containsKey(ch)) {
                    orderedMap.put(ch, '0');
                } else {
                    //当前元素已经存在，需要看添加到末尾是否更小
                    char next = orderedMap.get(ch);
                    if ('0' != next && ch > next) {
                        orderedMap.put(ch, '0');
                    } else {

                    }

//                    if (ch > lastChar) {
//                        orderedMap.remove(ch);
//                        orderedMap.add(ch);
//                        lastChar = ch;
//                    }
                }
            }

            StringBuilder res = new StringBuilder();
//            for (Character c : orderedMap) {
//                res.append(String.valueOf(c));
//            }
            return res.toString();
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.smallestSubsequence("cbacdcbc"));
    }

    public static void main(String[] args) throws Exception {
        LC1081 an = new LC1081();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
